package dynamicprogramming;

import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 15:18
 * 极客时间 40节
 */
public class DynamicProgrammingMethod1 extends Example1 {

    @Override
    public void f(int[] weight, int n, int w) {
        boolean[][] state = new boolean[n][w + 1];  // n行，代表n个物品；w+1列代表最终的重量
        // 第一个物品的两种情况
        state[0][0] = true; // 什么都不放
        if (weight[0] <= w) {
            state[0][weight[0]] = true; // 放第一个
        }
        // 第二种及后面的情况
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < w + 1; j++) {
                if (state[i - 1][j]) {
                    state[i][j] = true; // 不放的情况
                    // 放的情况
                    if (j + weight[i] <= w) {
                        state[i][j + weight[i]] = true;
                    }
                }
            }
        }
        //找出决策所有物品之后，总和最大的重量
        for (int i = w; i >= 0; i--) {
            if (state[n - 1][i]) {
                maxW = i;
                return;
            }
        }
    }

    @Test
    public void test() {
        f(weight, n, w);
        System.out.println(maxW);
    }

}
